\section{Problema 3}

\subsection{Enunciado}

Un n\'umero cuadrado es un n\'umero entero cuya ra\'iz cuadrada es tambi\'en entera. Por ejemplo 1, 4, 81 son n\'umeros
cuadrados. Dados dos n\'umeros $a$ y $b$ encontrar cu\'antos n\'umeros cuadrados hay entre $a$ y $b$ (inclusive).
\subsection{Introducci\'on}
Se nos pide encontrar la cantidad de n\'umeros cuadrados que hay en un intervalos cerrado.
Basicamente la soluci\'on est\'a en averiguar cuantos numeros del intervalo son cuadrados.
Como no disponemos de la funci\'on "sqrt" de C++ vamos a tener que implementarla para as\'i obtener el maximo y el minimo n\'umero cuadrado del intervalo $[a;b]$
\subsection{Correctitud}
Es facil ver que la raiz cuadrada de todos los numeros cuadrados  del intervalo $[a,b]$
caen dentro del intervalo $[\sqrt{a},\sqrt{b}]$, y que todos los elementos enteros del intervalo $[\sqrt{a},\sqrt{b}]$ son las raices de los numeros cuadrados del intervalo $[a,b]$. Por lo que la cantidad de numeros cuadrados en el intervalo $[a,b]$ es igual a la cantidad de numeros enteros que hay en $[\sqrt{a},\sqrt{b}]$.\\

Supongamos que a y b son n\'umeros cuadrados, entonces todos los enteros del intervalo \\
$E = [\sqrt{a},\sqrt{b}]$ elevados al cuadrado caen dentro de $[a,b]$ por lo que la respuesta seria $\#E$. 
El problema estaría en que pasa si alguno o ambos no son cuadrados, en el caso de $b$ no hay problema porque 
como el algoritmo para calcular raíz trunca para abajo el resultado decimal entonces la cota superior del intervalo $[..\lfloor\sqrt{b}\rfloor]$ 
elevado al cuadrado siempre es menor o igual que $b$. Sin embargo, si $a$ no es un cuadrado, el primer elemento del intervalo $[\lfloor\sqrt{a}\rfloor..]$ elevado al cuadrado no cae dentro dentro de $[a,b]$.
Esto se soluciona truncando hacia arriba el resultado de la raiz cuadrada para $a$. 
Esta solucion se implementa agregando un condicional que incremente en uno la raiz de $a$ si esta no es un cuadrado.
Por ultimo se devuelve la longitud del intervalo$[\lceil\sqrt{a}\rceil, \lfloor\sqrt{b}\rfloor]$.
\subsection{Pseudoc\'odigo}
\begin{algorithm}[H]
\caption{raiz(Int $num$)}
\begin{algorithmic}
\STATE $ i \leftarrow 0 $
\WHILE{$i*i \leftarrow num$}
\STATE $i \leftarrow i + 1$
\ENDWHILE
\RETURN $i-1$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[H]
\caption{numerosCuadrados(Int $a$, Int $b$)}
\begin{algorithmic}
\STATE $inferior \leftarrow raiz(a)$
\STATE $superior \leftarrow raiz(b)$
\IF{$inferior * inferior \neq a$}
\STATE $inferior \leftarrow inferior + 1$
\ENDIF
\RETURN $(superior - inferior) + 1$
\end{algorithmic}
\end{algorithm}


\subsection{An\'alisis de Complejidad}
Para un entero $a \geq 0$ el cuerpo del ciclo de la funcion raiz se repite $\sqrt{a}$ veces.
por lo que la funcion $raiz(a)$ tiene complejidad $\sqrt{a}{(\log_2 a)}^{2}$ para un tamaño de entrada $\log_2 a$. \\
Prueba:
\begin{itemize}
	\item $i\leftarrow 0$ es constante, por lo tanto $O(1)$
	\item el condicional del ciclo es $i*i \leq a$ es $(\log_2 i)*(\log_2 i) + \log_2 a$
	\item el cuerpo del ciclo es $i \leftarrow i + 1$ es $\log_2 i$
	\item devolver el resultado $ret \leftarrow i-1$ es $log_2 \sqrt{a}$
\end{itemize}
Como el cuerpo del ciclo se ejecuta $\sqrt{a}$ veces, su complejidad es
$$\sum_{i=0}^{\sqrt{a}} ({(log_2 i)}^{2} + \log_2 a + \log_2 i) =
\sqrt{a}(\log_2 a) + \sum_{i=0}^{\sqrt{a}} ({(\log_2 i)}^{2} + \log_2 i)$$
$${\leq}_{(i \leq a)} \sqrt{a}(\log_2 a) + \sum_{i=0}^{\sqrt{a}} ({(\log_2 a)}^{2} + \log_2 a)$$
$$= \sqrt{a}(\log_2 a) + \sqrt{a}{(\log_2 a)}^{2} + \sqrt{a}(\log_2 a) $$
$$= 2\sqrt{a}(\log_2 a) + \sqrt{a}{(\log_2 a)}^{2} \leq c\sqrt{a}{(\log_2 a)}^{2} \textrm{para algun c.} $$
Veamos que pasa con $raiz(a)$: $$ 1 + c\sqrt{a}{(\log_2 a)}^{2} + \log_2 a \leq c'\sqrt{a}{(\log_2 a)}^{2} \textrm{para algun c'.}$$
Por lo tanto $raiz(a) \in O(\sqrt{a}{(\log_2 a)}^{2})$ \\

La complejidad del algoritmo numerosCuadrados es $O(\sqrt{b}{(\log_2 b)}^{2})$\\
Prueba:
\begin{itemize}
	\item $inferior \leftarrow raiz(a)$ es $O(\sqrt{a}{(\log_2 a)}^{2})$
	\item $inferior \leftarrow raiz(b)$ es $O(\sqrt{b}{(\log_2 b)}^{2})$
	\item el condicional del if tiene complejidad $O(({\log_2 \sqrt{a})}^{2} + \log_2 a)$, pues una comparacion es lo mismo que hacer una resta y ver la diferencia
	\item en caso de que el condicional sea cierto, su implicacion(incrementar inferior) tiene complejidad $O(\log_2 \sqrt{a})$
	\item devolver el resultado tiene complejidad $O(\log_2 \sqrt{b} + \log_2 \sqrt{a})$ porque restar 2 numeros es lo mismo que sumarle el inverso aditivo al sumando.
\end{itemize}
Por lo tanto ejecutar numerosCuadrados toma:

$$\sqrt{a}{( \log_2 a)}^{2} + \sqrt{b}{( \log_2 b)}^{2} + {(\log_2 \sqrt{a})}^{2} + \log_2 a + \log_2 \sqrt{a} + \log_2 \sqrt{a} + \log_2 \sqrt{b} $$
$${\leq}_{a\leq b}   2\sqrt{b}{( \log_2 b)}^{2} + {(\log_2 \sqrt{b})}^{2} + \log_2 b + \log_2 \sqrt{b} + \log_2 \sqrt{b} + \log_2 \sqrt{b}$$
$$ = 2\sqrt{b}{( \log_2 b)}^{2} + {(\log_2 \sqrt{b})}^{2} + \frac{5}{2}\log_2 b \leq d\sqrt{b}{( \log_2 b)}^{2} \textrm{para algun d.}$$
Luego numerosCuadrado $\in O(\sqrt{b}{(\log_2 b)}^{2})$\\
Ahora poniendo todo en funcion del tamaño de la entrada(suponiendo el peor caso a=b pues en ese caso se calcula 2 veces la raiz del numero mas grande): 
$$T = \log_2 b + \log_2 b = 2\log_2 b \leftrightarrow {2}^{T} = {2}^{2\log_2 b} \leftrightarrow 2^{T} = {({2}^{\log_2 b})}^{2} \leftrightarrow 2^{T} = b^{2} \leftrightarrow {2}^{\frac{T}{2}} = b$$
Con $b = 2^{\frac{T}{2}}$ y numerosCuadrados $\in O(\sqrt{b}{(\log_2 b)}{2}) \rightarrow $\\
$$  \textrm{numerosCuadrados} \in O(  \sqrt{2^{\frac{T}{2}}}{(\log_2 {2}^{\frac{T}{2}})}^{2}  )\rightarrow$$
$$ \textrm{numerosCuadrados}\in O(  2^{\frac{T}{4}}{(\frac{T}{2})}^{2}  )\rightarrow $$
$$ \textrm{numerosCuadrados}\in O(  2^{\frac{T}{4}}{T}^{2}  )$$



\subsection{Mediciones}
No consideramos que haya peores o mejores casos, simplemente casos más grandes y casos más chicos. Al estar limitados por enteros de 32 bits el tamaño máximo de entrada es de 64 bits (2 enteros).

La escala del siguiente gráfico es logarítmica para poder apreciar mejor las curvas. Los puntos rojos representan los datos medidos, y la curva verde representa la complejidad calculada con anterioridad.

\includegraphics[width=\textwidth]{problema3/medicion.png}

\newpage